﻿#pragma once

#include <iostream>
#include <cassert>
#include <thread>
#include <mutex>
#include <algorithm>

// 控制页号的类型
#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#else
	// linux...
#endif // _WIN64


static const size_t MAX_BYTES = 256 * 1024; // thread 最大申请的内存大小为 256 KB
static const size_t N_FREE_LIST = 208; // thread cahce 中一共有 208 个桶

// 获取 obj 对象的 头部的 4/8 字节
static inline void*& NextObj(void* obj)
{
	return *(void**)obj;
}

class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);
		// 头插
		NextObj(obj) = _freelist;
		_freelist = obj;
	}

	//插入一段范围的对象到自由链表
	void PushRange(void* start, void* end)
	{
		assert(start);
		assert(end);

		//头插
		NextObj(end) = _freelist;
		_freelist = start;
	}

	void* Pop()
	{
		assert(_freelist);
		// 头删
		void* obj = _freelist;
		_freelist = NextObj(obj);
		return obj;
	}

	bool Empty()
	{
		return _freelist == nullptr;
	}
		
	size_t& MaxSize()
	{
		return _maxSize;
	}

private:
	void* _freelist = nullptr;
	size_t _maxSize = 1;// 初始值给成1，表示第一次申请一个内存对象
};


// 管理对齐规则和映射等关系
class SizeClass
{
public:
	// 根据 bytes 和 alignNUm 进行对齐
	//static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	//{
	//	size_t alignSize = 0;
	//	if (bytes % alignNum == 0)
	//	{
	//		// 申请的字节数是对其数的整数倍，无需对其
	//		alignSize = bytes;
	//	}
	//	else
	//	{
	//		// 因为向上取整，所以让 bytes / alingNum 的商 + 1就想上取整了，然后 在 乘 alignNum 即可
	//		alignSize = (bytes / alignNum + 1) * alignNum;
	//	}
	//	return alignSize;
	//}

	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		// 当前字节数 + 对其数 - 1 就永远到不了，对其数的下一个整数倍，但是 >= alignNum 的 
		// 当前的结果 是由 最大对其数的 位数 中的 其中几位 组合而成的
		// 再将 对其数 -1 取反，意味着最大对其数的 最高位不变，后面的低位全部取反
		// 在和 + 对其数 - 1 的结果 按位与，就只剩下 对其数了
		// 例如：[1-8] --> + 8-1 = 7 ===> [8-15], 7 取反 == 1000 & [8-15] == 8
		return (bytes + (alignNum - 1)) & ~(alignNum - 1);
	}

	// 获取向上对齐后的字节数
	static inline size_t RoundUp(size_t bytes)
	{

		// 整体控制在最多10%左右的内碎片浪费
		// [1,128]               8byte对齐        freelist[0,16)
		// [128+1,1024]          16byte对齐       freelist[16,72)
		// [1024+1,8*1024]       128byte对齐      freelist[72,128)
		// [8*1024+1,64*1024]    1024byte对齐     freelist[128,184)
		// [64*1024+1,256*1024]  8*1024byte对齐   freelist[184,208)
		assert(bytes <= MAX_BYTES);

		if (bytes <= 128)
		{
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024)
		{
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8 * 1024)
		{
			return _RoundUp(bytes, 128);
		}
		else if (bytes <= 64 * 1024)
		{
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 256 * 1024)
		{
			return _RoundUp(bytes, 8 * 1024);
		}
		else
		{
			// 理论上不会走到这里，避免程序出错到这里，我们直接断言结束
			assert(false);
			return -1;
		}
	}

	// 根据字节数和对其数判断 映射的位置
	//static inline size_t _Index(size_t bytes, size_t alignNum)
	//{
	//	if (bytes % alignNum == 0)
	//	{
	//		// 如果 bytes / alignNum 是整除的，说明当前字节的位置就是, 商 的 前一个
	//		// 例如：Bytes = 8 ,alignNum = 8 ==> bytes / alignNum == 1， 而 [1-8] 是 0 号桶
	//		return bytes / alignNum - 1;
	//	}
	//	else
	//	{
	//		// 否则，上就是 合适的位置
	//		// 1 / 8 == 0 
	//		return bytes / alignNum;
	//	}
	//}

	// 根据字节数和对其数的二进制次方判断 映射的位置
	static inline size_t _Index(size_t bytes, size_t align_shift)// align_shift 表好似对其数对应的次方数
	{
		// 当前的 bytes + 1 << align_shift) - 1 本质就是 bytes + 对其数 - 1，也就是刚好永远到不了，下一个对其数的倍数处
		// 他因为对其数 是 2^x，所以再将 上述的结果 >> align_shift 就是，对应桶的下一个位置 ，在 -1 即可
		return (((bytes + (1 << align_shift) - 1)) >> align_shift) - 1;
	}

	
	// 获取对应哈希桶的下标
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		// 每个区间有多少个 桶（链）
		static int grounp_array[4] = { 16, 56, 56, 56 };

		if (bytes <= 128)
		{
			return _Index(bytes, 3); // 2^3
		}
		else if (bytes <= 1024)
		{
			// 这里因为每个区间采用的对齐数不一样，说我我们 采用绝对映射
			// 最后为了映射的正确性，我们需要加上 前面的一段的 桶的个数
			return _Index(bytes - 128, 4) + grounp_array[0];// 2^4
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes - 1024, 7) + grounp_array[0] + grounp_array[1];// 2^7
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes - 8 * 1024, 10) + grounp_array[0] + grounp_array[1] + grounp_array[2];// 2^10
		}
		else if (bytes <= 256 * 1024)
		{
			return _Index(bytes - 64 * 1024, 13) + grounp_array[0] + grounp_array[1] + grounp_array[2] + grounp_array[3];// 2^13
		}
		else
		{
			// 为了避免程序出错走到这里
			assert(false);
			return -1;
		}
	}

	// thread cache 一次从 central cache 获取到的内存对象的个数
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		// size 越大，上限越小
		// size 越小，上限越大
		int num = MAX_BYTES / size;

		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;

		return num;
	}
};

// 管理以页为单位的大块内存
struct Span
{
	PAGE_ID _id = 0; // 大块内存的起始页号
	size_t _n = 0; // 当前 Span 管理大块内存的数量，即页数

	Span* _next = nullptr; //双链表结构
	Span* _prev = nullptr;

	size_t _useCount = 0; // 切好的小内存分给 thread cache 的数量
	void* _freelist = nullptr; // 管理切好小块内存的自由链表
};

// 双链表结构
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

		Span* prev = pos->_prev;
		Span* next = pos->_next;
		// 这里不是真的删除，只是将该 span 从双链表中删除，还给 page cache ,不需要 delete
		prev->_next = next;
		next->_prev = prev;
	}

private:
	Span* _head;
public:
	std::mutex _mtx; // 桶锁
};